public class BinarySearchTree {
	/**
	 * 搜索二叉树中序遍历是一个有序的
	 * 任意一个子树的左节点比根节点要小，右节点比跟节点要大。
	 */
	static class TreeNode {
		int val;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int val) {
			this.val = val;
		}
	}

	public int usedSize;
	public TreeNode root = null;

	public boolean insert(int val) {
		TreeNode node = new TreeNode(val);
		if (root == null) {
			root = node;
			this.usedSize++;
			return true;
		}
		TreeNode cur = root;
		TreeNode parent = null;
		while (cur != null) {
			if (cur.val < val) {
				parent = cur;
				cur = cur.right;
			} else if (cur.val > val) {
				parent = cur;
				cur = cur.left;
			} else {
				return false;
			}
		}
		//程序走到这里说明前面都没有返回，这里开始进行插入
		if (parent.val > val) {
			parent.left = node;
		} else {
			parent.right = node;
		}
		this.usedSize++;
		return true;
	}

	public void remove(int val) {
		if(root==null) {
			return ;
		}
		TreeNode cur = root;
		TreeNode parent = null;
		while (cur!= null) {
			if (cur.val < val) {
				parent = cur;
				cur = cur.right;
			} else if (cur.val > val) {
				parent = cur;
				cur = cur.left;
			} else {
				//程序走到这里说明已经找到这个节点，然后进行删除
				removeNode(parent,cur);
				return ;
			}
		}
	}
	private void removeNode (TreeNode parent,TreeNode cur) {
		if(cur.left==null) {
			//大的前提下cur的左边为空
			if(cur==root) {
				root=cur.right;
			} else {
				if(parent.left==cur) {
					parent.left=cur.right;
				} else {
					parent.right=cur.right;
				}
			}
		} else if(cur.right==null ) {
			if(cur==root) {
				root=cur.left;
			} else {
				if(parent.left==cur) {
					parent.left=cur.left;
				} else {
					parent.right=cur.left;
				}
			}
		} else {
			//两边都不为空
			//这里采用替罪羊的删除方法，在cur的左边的最大值或者是右边的最小值
			//cur现在所指向的是我们要删除的
			TreeNode target=cur.right;
			TreeNode targetParent=cur;
			while(target.left!=null) {
				targetParent=target;
				target=target.left;
			}
			cur.val=target.val;
			//此时target没有左树了，因为target是最后一个节点
			//此时还要进行判断
			//当target的没有左节点的时候，直接将target的值赋值给cur，此时要删除的是target，而且target没有左节点
			//只需要下面的哪一行代码

			//当cur.right有左孩子节点的时候，这时候需要将target节点的右孩子赋值给targetParent的左边
			if(target==targetParent.left) {
				targetParent.left=target.right;
			} else {
				targetParent.right = target.right;
			}
		}
	}
	public void display() {

	}
}
